"""
https://leetcode-cn.com/problems/rotate-image

给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。

说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
],

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

"""
from typing import List


class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        提示：
        对坐标 (i, j) 可以找到旋转 90 度后的新坐标为 (j, cols-i)，记之为 (i, j)->(j, cols-i)，
        那么，可以找到新坐标处的元素旋转后的新坐标。
        (i, j)->(j, cols-i)->(cols-i, cols-j)->(cols-j, i)->(i, j)
        图示过程见本目录下 method.jpg。

        Do not return anything, modify matrix in-place instead.
        """
        cols = len(matrix[0]) - 1
        for i in range(cols):
            for j in range(i, cols - i):
                tmp = [matrix[i][j], matrix[j][cols - i], matrix[cols - i][cols - j], matrix[cols - j][i]]
                matrix[j][cols - i] = tmp[0]
                matrix[cols - i][cols - j] = tmp[1]
                matrix[cols - j][i] = tmp[2]
                matrix[i][j] = tmp[3]